package com.qjc.demo.algorithm.回文链表;

/**
 * @ClassName: HuiWenLinkList
 * @Description: 回文链表
 * 1->2->3->3->2->1
 * 1->2->3->2->1
 * 上面两个都是回文链表，反过来和正过来是一样的
 * @Author: qjc
 * @Date: 2022/5/6 3:47 PM
 */
public class HuiWenLinkList {

    // 解题思路：找到中间节点，把后面的反转过来，然后前后进行对比（有两种情况：奇数个元素和偶数个元素）
    // 处理步骤如下：
    // 定义快慢指针，快指针一次移动两步，慢指针一次移动一步
    // 当快指针移动到最后，那么慢指针就移动到了中间，如果此时快指针不为空，则说明一共有奇数个元素，则让慢指针再次后移一个元素
    // 然后快指针指向头结点，慢指针的链表进行反转，反转后的链表跟快指针进行比较，直到慢指针为空，如果都是相等的那么它就是回文链表
    public static boolean isHuiWenLink(HuiWenLinkNode head) {
        // 定义快慢指针
        HuiWenLinkNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;// 快指针一次移动两步
            slow = slow.next; // 慢指针一次移动一步
        }

        if (fast != null) {
            // 说明是奇数个，将慢指针往后移一步，然后反转
            slow = slow.next;
        }
        slow = reverse(slow);
        // 将快指针指向头结点
        fast = head;
        while (slow != null) {
            if (fast.data != slow.data) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    private static HuiWenLinkNode reverse(HuiWenLinkNode head) {
        HuiWenLinkNode currNode = head;
        HuiWenLinkNode preNode = null;
        while (currNode != null) {
            HuiWenLinkNode next = currNode.next;
            currNode.next = preNode;
            preNode = currNode;
            currNode = next;
        }
        return preNode;
    }

    public static void main(String[] args) {
        HuiWenLinkNode n1 = new HuiWenLinkNode(1);
        HuiWenLinkNode n2 = new HuiWenLinkNode(2);
        HuiWenLinkNode n3 = new HuiWenLinkNode(3);
        HuiWenLinkNode n4 = new HuiWenLinkNode(3);
        HuiWenLinkNode n5 = new HuiWenLinkNode(2);
        HuiWenLinkNode n6 = new HuiWenLinkNode(1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = null;

        System.out.println(isHuiWenLink(n1));
    }


}

class HuiWenLinkNode {
    int data;
    HuiWenLinkNode next;

    public HuiWenLinkNode(int data) {
        this.data = data;
    }
}